//有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示
//水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。 
//
// 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 
//xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。 
//
// 给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。 
// 
//
// 示例 1： 
//
// 
//输入：points = [[10,16],[2,8],[1,6],[7,12]]
//输出：2
//解释：气球可以用2支箭来爆破:
//-在x = 6处射出箭，击破气球[2,8]和[1,6]。
//-在x = 11处发射箭，击破气球[10,16]和[7,12]。 
//
// 示例 2： 
//
// 
//输入：points = [[1,2],[3,4],[5,6],[7,8]]
//输出：4
//解释：每个气球需要射出一支箭，总共需要4支箭。 
//
// 示例 3： 
//
// 
//输入：points = [[1,2],[2,3],[3,4],[4,5]]
//输出：2
//解释：气球可以用2支箭来爆破:
//- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
//- 在x = 4处射出箭，击破气球[3,4]和[4,5]。 
//
// 
//
// 
//
// 提示: 
//
// 
// 1 <= points.length <= 10⁵ 
// points[i].length == 2 
// -2³¹ <= xstart < xend <= 2³¹ - 1 
// 
// Related Topics 贪心 数组 排序 👍 595 👎 0

package leetcode.editor.cn;

import java.util.Arrays;
import java.util.Comparator;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution452 {
    public int findMinArrowShots(int[][] points) {
//        Arrays.sort(points,  (o1,o2) -> o1[0] == o2[0] ? Integer.compare(o1[1], o2[1]):Integer.compare(o1[0], o2[0]));
        Arrays.sort(points,  (o1,o2) -> o1[0] > o2[0] ? 1 : -1); //可以通过
        int result = 1;
        for(int i = 1; i< points.length; i++){
            if(points[i][0] > points[i-1][1]){
                result++;
            } else {
                points[i][1] = Math.min(points[i-1][1], points[i][1]);
            }
        }
        return result;
    }
        /**
         * //这样写是有问题的，例如【1，3】，【1，9】，【2，5】,其preIndex变为了5,实际是3，因为preIndex始终比较的是当前一个
         * 和前一个，但是有可能正确的preIndex是当前的前两个的右边界
         * @param points
         * @return
         */
    public int findMinArrowShots2(int[][] points) {
//        Arrays.sort(points,  (o1,o2) -> o1[0] - o2[0]);
        Arrays.sort(points,  (o1,o2) -> o1[0] == o2[0] ? Integer.compare(o1[1], o2[1]):Integer.compare(o1[0], o2[0]));
        int preIndex = points[0][1];
        int result = 1;
        for(int i = 1; i < points.length; i++){
            if(points[i][0] > preIndex ){ //气球没有重合
                result++;
                preIndex = points[i][1];
            } else { //重合了，取重合气球的最小右边界
                //这样写是有问题的，例如【1，3】，【1，9】，【2，5】,其preIndex变为了5,实际是3，因为preIndex始终比较的是当前一个
                    //    和前一个，但是有可能正确的preIndex是当前的前两个的右边界
//                preIndex = Math.min(points[i-1][1], points[i][1]);
                preIndex = Math.min(preIndex, points[i][1]); //应该将当前的右边界和前面所有重叠气球右边界的最小值（即preIndex)进行比较
            }
        }
        return result;
    }

    public static void main(String[] args) {
//        new Solution().findMinArrowShots(new int[][]{{10,16},{2,8},{1,6},{7,12}});
//        new Solution452().findMinArrowShots(new int[][]{{-2147483646,-2147483645},{2147483646,2147483647}});
//        new Solution().findMinArrowShots(new int[][]{{3,9},{7,12},{3,8},{6,8},{9,10},{2,9},{0,9},{3,9},{0,6},{2,8}});
//        new Solution452().findMinArrowShots(new int[][]{{9,12},{1,10},{4,11},{8,12},{3,9},{6,9},{6,7}});
//        new Solution452().findMinArrowShots(new int[][]{{1,9},{7,16},{2,5},{7,12},{9,11},{2,10},{9,16},{3,9},{1,3}});
    }
}
//leetcode submit region end(Prohibit modification and deletion)
